package dp.jichu;

/**
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
 *
 * 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
 *
 *
 * 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 *
 * 输入：cost = [10, 15, 20]
 * 输出：15
 * 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
 *
 * 一定要注意理解体力消耗这句话，你跨过台阶，就消耗掉该台阶的体力
 * 比如下标为1 到 下标为2的跨越，消耗的是15而不是20，所以当你站在起点时，0或者1位置，此时体力消费为0
 * 而且站在顶端时，20也是不消耗的。解法看方法1
 *
 * 这里其实两两种理解方式
 *
 * 还以为理解为，站在哪个台阶上，就消耗多少体力，到达顶端不消耗
 * 看解法2
 * 1.确定 dp 数组以及下标的含义
 *  使用一维数组 dp[i] 来记录状态
 *  dp[i] 的定义为，到达第 i 个台阶所花费的最少体力为 dp[i] ，注意第一步一定是要花费
 * 2.确定递推公式
 *  根据题意可知，得到 dp[i] 有两种途径，即 dp[i - 1] 和 dp[i - 2] ，也就是对应上一步是爬一个楼梯上来的还是两个爬两个楼梯上来的。
 *  要求最小值，那么一定是 dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] ，最后一个 cost[i] 对应题目中的要求——每当你爬上一个阶梯你需要支付相应的体力值
 * 3.dp 数组如何进行初始化
 *  我们从递推公式可以看出，要求出 dp[i] 我们需要知道 dp[i - 1] 和 dp[i - 2] ，因此我们需要初始化dp[0] 和 dp[1] 即可。
 *  dp[0] = cost[0] , dp[1] = cost[1]
 * 4.确定遍历顺序
 *  本题的遍历顺序很简单，因为是模拟台阶，而且 dp[i] 是通过 dp[i - 1] 和 dp[i - 2] 推出，所以从前到后遍历 cost 数组即可。
 *
 *
 * dp[i] 代表到达i位置时，最低花费的体力
 */
public class leetCode746_minCostClimbingStairs {

    public static void main(String[] args) {
        leetCode746_minCostClimbingStairs a = new leetCode746_minCostClimbingStairs();
        int[] aa = {10,15,20,30,20,49};
        int i = a.minCostClimbingStairs(aa);
        System.out.println(i);
    }

    public int minCostClimbingStairs(int[] cost) {

        int length = cost.length;
        int[] dp = new int[length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
        }
        return dp[length];

    }

    public int minCostClimbingStairs2(int[] cost) {
        int length = cost.length;
        int[] dp = new int[length];
        dp[0] = cost[0]; // 从哪里出发，站在哪儿，就消耗对应的体力
        dp[1] = cost[1];
        for (int i = 2; i < length; i++) {
            dp[i] = Math.min(dp[i - 1],dp[i - 2]) + cost[i];
        }
        return Math.min(dp[length - 1],dp[length - 2]);
    }


}
